/**
 * 45. 跳跃游戏 II
 * 
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 * 
 * 示例 1:
 * 输入: [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 * 
 * 示例 2:
 * 输入: [2,3,0,1,4]
 * 输出: 2 
 * 提示:
 * 
 * 1 <= nums.length <= 1000
 * 0 <= nums[i] <= 10^5
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */
package zw;

public class T45 {
	// 动态规划
	public int jump(int[] nums) {
		int size = nums.length;
		int[] minSteps = new int[size]; // 保存跳到该位置需要的最小值
		
		for(int i = 0; i < size; i++) {
			minSteps[i] = Integer.MAX_VALUE;
		}
		
		minSteps[0] = 0;
		for(int i = 0; i < size; i++) {
			for(int j = 1; j <= nums[i]; j++) {
				if(i+j < size && minSteps[i+j] > minSteps[i]+1) {
					minSteps[i+j] = minSteps[i] + 1;
				}
			}
		}
		return minSteps[size-1];
    }
	
	// 贪心算法
	public int jump2(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
	
	public static void main(String[] args) {
		T45 t45 = new T45();
		System.out.println(t45.jump2(new int[]{0}));
	}
}
